package arr;

/**
 * @author yyz
 * @create 2023-11-08 14:00
 */
public class 二分查找 {
    public static void main(String[] args) {
        二分查找 x = new 二分查找();
        System.out.println(x.binarySearchRightmost2(new int[]{1, 2, 2, 3, 45, 45, 69}, 44));
    }

    /**
     * 二分查找基础版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回索引, 找不到返回-1
     */
    private int binarySearch(int[] a, int target) {
        int i = 0, j = a.length - 1;  // 初始化左边界 i 为 0，右边界 j 为数组 a 的最后一个索引位置

        int m;  // 用于存储中间索引位置的变量

        while (i <= j) {  // 当左边界小于等于右边界时，执行二分查找
            m = (i + j) >>> 1;  // 计算中间索引位置（无符号右移一位相当于除以2，即二分查找的核心）

            if (a[m] < target) {  // 如果中间元素小于目标值
                i = m + 1;  // 更新左边界，将左边界移到中间索引的右侧
            } else if (target < a[m]) {  // 如果中间元素大于目标值
                j = m - 1;  // 更新右边界，将右边界移到中间索引的左侧
            } else {  // 如果中间元素等于目标值
                return m;  // 返回目标值的索引位置
            }
        }

        return -1;  // 如果未找到目标值，返回 -1 表示目标值不在数组中

    }

    /**
     * 二分查找改动版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回索引, 找不到返回-1
     */
    private int binarySearch2(int[] a, int target) {
        int i = 0, j = a.length;  // 初始化左边界 i 为 0，右边界 j 为数组 a 的最后一个索引位置的下一个位置

        int m;  // 用于存储中间索引位置的变量

        while (i < j) {  // 当左边界小于右边界时，执行二分查找
            m = (i + j) >>> 1;  // 计算中间索引位置（无符号右移一位相当于除以2，即二分查找的核心）

            if (a[m] < target) {  // 如果中间元素小于目标值
                i = m + 1;  // 更新左边界，将左边界移到中间索引的右侧
            } else if (target < a[m]) {  // 如果中间元素大于目标值
                j = m;  // 更新右边界，将右边界移到中间索引的左侧
            } else {  // 如果中间元素等于目标值
                return m;  // 返回目标值的索引位置
            }
        }

        return -1;  // 如果未找到目标值，返回 -1 表示目标值不在数组中


    }

    /**
     * 二分查找平衡版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回索引, 找不到返回-1
     */
    private int binarySearch3(int[] a, int target) {
        int i = 0, j = a.length;

        int m;

        while (1 < j - i) {  // 判断是否只有一个需要判断的值
            m = (i + j) >>> 1;

            if (a[m] <= target) {
                i = m;
            } else {
                j = m;
            }
        }

        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }


    }

    /**
     * 二分查找 Leftmost
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回最左侧索引, 找不到返回-1
     */
    private int binarySearchLeftmost(int[] a, int target) {
        int i = 0, j = a.length - 1;

        int m;
        int candidate = -1;

        while (i <= j) {  // 当左边界小于等于右边界时，执行二分查找
            m = (i + j) >>> 1;  // 计算中间索引位置（无符号右移一位相当于除以2，即二分查找的核心）

            if (a[m] < target) {  // 如果中间元素小于目标值
                i = m + 1;  // 更新左边界，将左边界移到中间索引的右侧
            } else if (target < a[m]) {  // 如果中间元素大于目标值
                j = m - 1;  // 更新右边界，将右边界移到中间索引的左侧
            } else {  // 如果中间元素等于目标值
                candidate = m;
                j = m - 1;
            }
        }

        return candidate;

    }

    /**
     * 二分查找 Leftmost 改动版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回>=target的最靠左索引
     */
    private int binarySearchLeftmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;

        int m;

        while (i <= j) {
            m = (i + j) >>> 1;

            if (a[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }

        return i;

    }

    /**
     * 二分查找 Rightmost
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回最右侧索引, 找不到返回-1
     */
    private int binarySearchRightmost(int[] a, int target) {
        int i = 0, j = a.length - 1;

        int m;
        int candidate = -1;

        while (i <= j) {  // 当左边界小于等于右边界时，执行二分查找
            m = (i + j) >>> 1;  // 计算中间索引位置（无符号右移一位相当于除以2，即二分查找的核心）

            if (a[m] < target) {  // 如果中间元素小于目标值
                i = m + 1;  // 更新左边界，将左边界移到中间索引的右侧
            } else if (target < a[m]) {  // 如果中间元素大于目标值
                j = m - 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }

        return candidate;

    }

    /**
     * 二分查找 Rightmost 改动版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回<= target的最靠右的索引
     */
    private int binarySearchRightmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;

        int m;

        while (i <= j) {  // 当左边界小于等于右边界时，执行二分查找
            m = (i + j) >>> 1;  // 计算中间索引位置（无符号右移一位相当于除以2，即二分查找的核心）

            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }

        return i - 1;

    }
}
